#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
	vector<int> nextArr(string& str) {
		if (str.size() == 1) return{ -1 };
		vector<int> nexts(str.size());
		nexts[0] = -1, nexts[1] = 0;
		for (int i = 2, t; i < str.size(); i++) {
			t = nexts[i - 1];
			while (str[i - 1] != str[t] && t > 0) {
				t = nexts[t];
			}
			if (str[i - 1] == str[t])
				nexts[i] = t + 1;
			else
				nexts[i] = 0;
		}
		return nexts;
	}
	int strStr(string haystack, string needle) {
		//kmp
		auto arrNext = nextArr(needle);
		int i1 = 0; int i2 = 0;
		while (i1 < haystack.size() && i2 < needle.size()) {
			if (haystack[i1] == needle[i2]) {
				i1++; i2++;
			}
			else if (i2 == 0) i1++;
			else {
				i2 = arrNext[i2];
			}
		}
		return i2 == needle.size() ? i1 - needle.size() : -1;

	}
};